//
// Created by Lenovo on 2024/3/14.
//
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

    int n;
    //并查集
    vector<int> p;

    int find(int x){
        if(x==p[x]) return x;
        else return p[x]=find(p[x]);
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        n=edges.size();
        p=vector<int>(n+1,0);
        for(int i=1;i<=n;i++) p[i]=i;
        vector<vector<int>> res;
        for(int i=0;i<edges.size();i++){
            int rootu=find(edges[i][0]);
            int rootv=find(edges[i][1]);
            if(rootu!=rootv){
                //两个顶点不是一个集合的
                p[rootu]=rootv;
            }else{
                //两个顶点是一个集合的，再加入就形成环了，所以去掉这条边
                vector<int> list;
                list.push_back(edges[i][0]);
                list.push_back(edges[i][1]);
                //将所有加入后形成环的变记录
                res.push_back(list);
                //要返回edges里尽可能靠后的边
                p[rootu]=rootv;
            }
        }
        return res[res.size()-1];
    }
};